1. Field of Invention
The present invention generally relates to a biometric identification system. More specifically, the present invention relates to the incremental modification of hierarchically indexed features in an identification registration system.
2. Description of Related Art
Biometrics refers to the use of intrinsic human traits for personal identification purposes. That is, a person may be identified by one or a combination of multiple different personal trait characteristics of that person. Examples of such personal traits are a fingerprint, a hand print (length and thickness of the fingers, size of the hand itself), a retina scan (pattern of blood vessels in the eye), an iris scan, a facial photograph, a blood vessel pattern (vein pattern), a voice print, a dynamic signature (the shape and time pattern for writing a signature), or a keystroke pattern (key entry timing).
An example fingerprint biometrics for personal identification is illustrated in U.S. Pat. No. 6,041,133 to Califano et al., which illustrates the identification of distinguishing characteristics, or token, based on the shapes of fingerprints. The identified tokens are then organized in a suitable searching format. Examples of using a hierarchical tree to organize identifying tokens for purposes of object recognition using a voting method is illustrated in U.S. Pat. No. 7,680,748 to Heisele et al.
Of particular interest regarding the present invention, however, are biometric identification techniques that use blood vessels, or veins, for personal identification. A method for automatically identifying blood vessels in a diagnostic image is described in U.S. Pat. No. 7,343,032 and an example of a technique for obtaining diagnostic images of blood vessels from a human eye for personal identification (ID) purposes is shown in U.S. Pat. No. 6,569,104. Another example provided in U.S. Pub. No. 2010/0045788 describes the use of visible and near infrared light to acquire diagnostic images of a palm print image for personal identification. A technique for using vein authentication on a finger for identification purposes is described in U.S. Pub. No. 2010/0198078.
Various techniques are known for identifying specific pattern structures in diagnostic images. One technique for identifying blood vessel patterns is by means of path-based tree matching, such as described in U.S. Pat. No. 7,646,903. Tree matching algorithms require tree structures as input. This structure describes the tree as a series of branches interconnected through branch points. Several known algorithms can be used to obtain the tree structure including tracking, segmentation, and skeletonization. Once the tree structure is obtained, a matching algorithm operates directly on the structure and any data contained therein.
A difficulty associated with using a tree structure is that modification of an existing tree requires access to all the data used in its original construction. Thus, once a tree is constructed, it cannot easily be modified to accommodate a change in data. In a personal identification (ID) system, for example, once an initial group of persons are registered, it is not a straight forward problem to register a new person or to remove a person from registration. The new person's identification data needs to be incorporated into the existing hierarchical tree, but this would typically require that the existing tree be removed and replaced by a new tree constructed from the new individual's identification data plus the identification data of the previous group of registered persons. Similarly, if a person from the original group is to be removed from the registration list, the existing tree would typically be replaced by new tree constructed from the characteristic data of the remaining individuals in the registration list. This process is not optimal since it requires storing of all original characteristic data of all registered persons, which poses a security risk, and requires additional computation resources.
Methods have been proposed for incrementally modifying an existing hierarchical tree without having to reconstruct a new tree. Such an incremental approach is described in “Efficient Object Recognition and Image Retrieval for Large-Scale Applications”, Thesis MIT 2008, ME of EECS by John Jaesung Lee. Such systems, however, still require access to all original data for identifying the tree nodes that need modification, and how to best modify the nodes. Such methods thus require access to additional information not available in the existing tree. Of more importance in the present application, existing incremental three methods cannot handle tree models having registration information.
It is an object of the present invention to provide an incremental tree method for tree models having registration information.
Another object of the present invention is to provide an efficient method of applying tree matching to biometric applications.
Another object of the present invention is to provide a hierarchical approach that not only identifies the closest matching vein pattern to a query, but also has the ability to reliability and efficiently reject a false positive identification.